/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-11-08
 * Time: 10:35
 */

import java.util.Arrays;

/**
 * 矩阵链乘问题的动态规划实现
 * 功能：计算矩阵链的最优乘法顺序，返回最少乘法次数和具体括号化方案
 */
import java.util.Arrays;

import java.util.Scanner;

public class MatrixChainMultiplication {

    // 计算矩阵链乘的最优解
    // 参数p: 矩阵维度数组，p[i]表示第i个矩阵的行数，p[i+1]表示第i个矩阵的列数
    // 返回值: 长度为2的数组，第一个元素是最优计算次数，第二个元素是括号化方案字符串
    public static Object[] matrixChainOrder(int[] p) {
        int n = p.length - 1; // 矩阵的数量
        int[][] m = new int[n + 1][n + 1]; // 存储最优计算次数
        int[][] s = new int[n + 1][n + 1]; // 存储最优分割点

        // 单个矩阵的计算次数为0
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }

        // l表示矩阵链的长度
        for (int l = 2; l <= n; l++) {
            // i表示矩阵链的起始索引
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1; // j表示矩阵链的结束索引
                m[i][j] = Integer.MAX_VALUE;

                // k表示分割点，尝试所有可能的分割
                for (int k = i; k < j; k++) {
                    int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    // 如果找到更优的解，更新最优计算次数和分割点
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }

        // 构建括号化方案
        String bracket = buildBracket(s, 1, n);

        return new Object[]{m[1][n], bracket};
    }

    // 递归构建括号化方案
    private static String buildBracket(int[][] s, int i, int j) {
        if (i == j) {
            return "A" + i;
        } else {
            return "(" + buildBracket(s, i, s[i][j]) + buildBracket(s, s[i][j] + 1, j) + ")";
        }
    }

    // 打印矩阵链的信息和最优解
    public static void printResult(int[] p, int caseNum) {
        System.out.println("测试案例 " + caseNum + ":");
        System.out.print("矩阵维度: ");
        for (int i = 0; i < p.length; i++) {
            System.out.print(p[i] + " ");
        }
        System.out.println();

        System.out.print("矩阵: ");
        for (int i = 1; i < p.length; i++) {
            System.out.print("A" + i + "(" + p[i-1] + "," + p[i] + ") ");
        }
        System.out.println();

        Object[] result = matrixChainOrder(p);
        System.out.println("最优计算次数: " + result[0]);
        System.out.println("最优括号化方案: " + result[1]);
        System.out.println("----------------------------------------");
    }

    public static void main(String[] args) {
        // 测试案例1: 3个矩阵
        int[] p1 = {10, 30, 5, 60};
        printResult(p1, 1);

        // 测试案例2: 4个矩阵
        int[] p2 = {30, 35, 15, 5, 10};
        printResult(p2, 2);

        // 测试案例3: 5个矩阵
        int[] p3 = {40, 20, 30, 10, 30, 50};
        printResult(p3, 3);

        // 测试案例4: 6个矩阵
        int[] p4 = {10, 20, 30, 40, 50, 60, 70};
        printResult(p4, 4);

        // 测试案例5: 7个矩阵
        int[] p5 = {5, 10, 3, 12, 5, 50, 6, 7};
        printResult(p5, 5);

        // 测试案例6: 8个矩阵
        int[] p6 = {3, 4, 2, 5, 7, 3, 8, 6, 1};
        printResult(p6, 6);

        // 允许用户输入自定义矩阵链
        Scanner scanner = new Scanner(System.in);
        System.out.print("是否要输入自定义矩阵链? (y/n): ");
        if (scanner.next().equalsIgnoreCase("y")) {
            System.out.print("请输入矩阵维度数量(至少2个): ");
            int n = scanner.nextInt();
            int[] p = new int[n];
            System.out.println("请输入" + n + "个维度值:");
            for (int i = 0; i < n; i++) {
                p[i] = scanner.nextInt();
            }
            printResult(p, 7);
        }
        scanner.close();
    }
}